package Sort;

import java.util.Arrays;

public class HeadSort2 {
    public static void main(String[] args) {
        int[] arr = new int[]{1,3,5,2,4,6,0};
        headSort2(arr);
        System.out.println(Arrays.toString(arr));
    }
  public static void createBigHead(int[] arr){
      for(int parent = (arr.length-2)/2;parent>=0;parent--){
          shiftDown(arr,parent,arr.length);
      }
  }

  public static void shiftDown(int[] arr,int parent,int len){
      //时时刻刻要记得边界情况
      int child = 2*parent+1;
      if(child + 1 < len && arr[child] < arr[child+1]){
          child++;
      }
      while (child < len){
          if(arr[parent] < arr[child]){
              swap(arr,parent,child);
              parent = child;
              child = 2*parent+1;
          }else{
              break;
          }
      }
  }

  public static void headSort2(int[] arr){
        createBigHead(arr);
      int end = arr.length-1;
      while (end >= 0){
          swap(arr,0,end);
          shiftDown(arr,0,end);
          end--;
      }
  }




    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
